package com.wen.Part6.GraphAlgorithm.impl;

import com.wen.Part6.DataStructure.Graph;
import com.wen.Part6.GraphAlgorithm.GraphAlgorithm;

import java.util.ArrayDeque;
import java.util.Arrays;

public class SPFA implements GraphAlgorithm {
    private String start;

    public SPFA(String start) {
        this.start = start;
    }

    @Override
    public Object solve(Graph g) {
        int[] dist = new int[g.getSize()];
        int[] path = new int[g.getSize()];
        int[] repeat = new int[g.getSize()];  // 元素入队时不应该在队中

        Arrays.fill(dist,999);  // 初始化距离
        int startIndex = g.key2Index(start);
        dist[startIndex] = 0;
        for (int i = 0; i < g.getSize(); i++) {    // 初始化路径
            path[i] = i;
        }

        ArrayDeque<Integer> queue = new ArrayDeque<>();  // 创建队列并初始化队列
        queue.offer(startIndex);
        repeat[startIndex] = 1;  // 元素入队，并标记元素在队列中

        while (!queue.isEmpty()){
            Integer head = queue.poll();
            repeat[head] = 0;
            // 每出队一个元素后，对该元素松弛，将松弛成功的元素入队
            for (Integer next : g.getAccessible(head)) {
                if (dist[head] + g.getWeight(head,next) < dist[next]){
                    dist[next] = dist[head] + g.getWeight(head,next);
                    path[next] = head;
                    if (repeat[next] == 0){  // 如果元素不再队列中
                        queue.offer(next);
                        repeat[next] = 1; // 元素入队，并标记元素在队列中
                        
                    }
                }
            }
        }

        System.out.println(Arrays.toString(path));
        System.out.println(Arrays.toString(dist));
        return null;
    }
}
